package leetcode.code0437;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.tree.TreeNode;

public class Solution1 extends Solution437 {

	private int ans;// 答案
	private int target;// 预期达到的累加和

	@Override
	public int pathSum(TreeNode root, int sum) {
		ans = 0;// 开始时答案为0
		target = sum;// 期望的累加和
		// 当前节点的累加和,这个累加和有几个.存在负数,所以这个值可能有多个.
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, 1);
		this.path(root, 0, map);// root之前,累加和是0
		return ans;
	}

	public void path(TreeNode root, int sum, Map<Integer, Integer> map) {
		if (root == null)
			return;
		// 设当前节点B, sum是从root到B的累加和
		sum += root.val;
		// 如果满足条件,收集结果,sum是包括root的结果,即从root到B的累加和是满足条件的,结果+1
//		if (sum == target)
//			ans++;
		// 尝试收集不包括root的结果,
		// 看看map中是否存在sum-target,设sum-target=y
		// 如果map中存在y,说明从root到中间某一个(或多个)节点A的累加和是y,则sum-y=target
		// 即`root到B的累加和` - `root到A的累加和` 满足条件, (存在负数,可能有多个)
		// 即A到B的累加和满足条件,区间A到B,满足要求
		ans += map.getOrDefault(sum - target, 0);// 有就加数,没就加0
		// root到当前节点的累加和是sum,累加和为sum的结果增加1.
		// 就是当前这个节点产生的影响.当前节点,对子子节点的计算,有影响.
		map.put(sum, map.getOrDefault(sum, 0) + 1);
		this.path(root.left, sum, map);
		this.path(root.right, sum, map);
		// 回溯,递归返回到上一层,取消当前节点的影响,当前节点,对父节点,不应有影响(有就错了).
		map.put(sum, map.getOrDefault(sum, 0) - 1);
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();// bug
		so.debug4();// bug
		so.debug5();// bug
		so.debug6();
		so.debug7();
		so.debug8();
		so.debug9();
		so.debug10();
	}

}
